/**
 * 
 */
package string.passed2;

import java.util.List;
import java.util.Map;
import java.util.HashMap;
import java.util.ArrayList;

import utils.PrintUtils;

/**
 * @author Michael
 * You are given a string, S, and a list of words, L, 
 * that are all of the same length. Find all starting indices 
 * of substring(s) in S that is a concatenation of each word 
 * in L exactly once and without any intervening characters.
 * For example, given:
 * S: "barfoothefoobarman"
 * L: ["foo", "bar"]
 * You should return the indices: [0,9].
 * (order does not matter).
 */
public class SubstringWithConcatenationOfAllWords {

    public List<Integer> findSubstring2a(String s, String[] words) {
    	List<Integer> result = new ArrayList<>();
        if (s == null || s.isEmpty() || words == null || words.length == 0) {
        	return result;
        }
    	
        int wordSize = words[0].length();
        Map<String, Integer> counts = new HashMap<>();
        for (String word : words) {
        	counts.put(word, counts.containsKey(word) ? counts.get(word) + 1 : 1);
        }
        
        for (int i = 0; i + words.length * wordSize <= s.length(); i++) {
        	if (counts.containsKey(s.substring(i, i + wordSize))) {
        		Map<String, Integer> found = new HashMap<>();
        		for (int j = 0; j < words.length; j++) {
        			int index = i + j * wordSize;
        			String word = s.substring(index, index + wordSize);
        			found.put(word, found.containsKey(word) ? found.get(word) + 1 : 1);
        		}
         		if (counts.equals(found)) {
        			result.add(i);
         		}
        	}
        }
        
        return result;
    }
    
    public List<Integer> findSubstring2b(String s, String[] words) {
    	List<Integer> result = new ArrayList<>();
        if (s == null || s.isEmpty() || words == null || words.length == 0) {
        	return result;
        }
    	
        int wordSize = words[0].length();
        Map<String, Integer> counts = new HashMap<>();
        for (String word : words) {
        	counts.put(word, counts.containsKey(word) ? counts.get(word) + 1 : 1);
        }
        
        loop: for (int i = 0; i + words.length * wordSize <= s.length(); i++) {
        	if (counts.containsKey(s.substring(i, i + wordSize))) {
        		Map<String, Integer> found = new HashMap<>();
        		for (int j = 0; j < words.length; j++) {
        			int index = i + j * wordSize;
        			String word = s.substring(index, index + wordSize);
        			found.put(word, found.containsKey(word) ? found.get(word) + 1 : 1);
        			if (!counts.containsKey(word) || found.get(word) > counts.get(word))
        			    continue loop;
        		}
        // 		if (counts.equals(found)) {
        		result.add(i);
        // 		}
        	}
        }
        
        return result;
    }
	
	public static List<Integer> findSubstring1(String str, String[] list) {
		assert (str!= null && !str.isEmpty());
		assert (list.length > 0);
		
		List<Integer> result = new ArrayList<Integer>();
		Map<String, Integer> counter = new HashMap<String, Integer>();
		for (String word : list) {
			if (counter.containsKey(word)) {
				counter.put(word, counter.get(word) + 1);
			}
			else {
				counter.put(word, 1);
			}
		}
		
		int wordSize = list[0].length();
		loop: for (int i = 0; i < str.length() - list.length * wordSize; i++) {
			String sub = str.substring(i, i + wordSize);
			if (counter.containsKey(sub)) {
				Map<String, Integer> found = new HashMap<String, Integer>();
				found.put(sub, 1);
				for (int j = i + wordSize; j < i + list.length * wordSize; j = j + wordSize) {
					String postfix = str.substring(j, j + wordSize);
					if (!counter.containsKey(postfix)) {
						continue loop;
					}
					if (!found.containsKey(postfix)) {
						found.put(postfix, 1);
					}
					else {
						found.put(postfix, found.get(postfix) + 1);
					}
					
					if (found.get(postfix) > counter.get(postfix)) {
						continue loop;
					}
				}
				result.add(i);
			}
		}
		
		return result;
	}
	
	
    public static List<Integer> findSubstring(String S, String[] L) {  
    	List<Integer> ans = new ArrayList<Integer>();
    	int m = L[0].length();
    	Map<String, Integer> count = new HashMap<String, Integer>(); 
    	Map<String, Integer> found = new HashMap<String, Integer>();
    	for (String l : L) {
    		if (count.get(l) == null) 
    			count.put(l, 1); 
    		else count.put(l, count.get(l) + 1);
    	}
    	
    	loop: for (int i = 0; i <= S.length() - L.length * m; i++) {
    		String sub = S.substring(i, i + m);
    		if (count.get(sub) != null) {
    			found.clear();
    			found.put(sub, 1);
    			for (int j = 1; j < L.length; j++) {
    				int s = i + j * m;
    				sub = S.substring(s, s + m); 
    				Integer toFind = count.get(sub);
    				if (toFind == null) 
    					continue loop; 
    				Integer foundVal = found.get(sub);        
    				int k = foundVal == null ? 1 : foundVal + 1;    
    				if (k > toFind) 
    					continue loop;               
    				found.put(sub, k);                
    			}               
    			ans.add(i); 
    		}       
    	}         
    	return ans; 
    }
    
	/**
	 *  *http://discuss.leetcode.com/questions/210/substring-with-concatenation-of-all-words
	 */
	// TODO this solution did not work
	public List<Integer> findSubstringLC(String S, String[] L) {
		HashMap<String, Integer> hasFound = new HashMap<String, Integer>();
		HashMap<String, Integer> needToFind = new HashMap<String, Integer>();
		int counter = 0;
		int wordLen = L[0].length();
		List<Integer> results = new ArrayList<Integer>();

		for (String word : L) {
			if (!needToFind.containsKey(word)) {
				needToFind.put(word, 1);
			} else {
				needToFind.put(word, needToFind.get(word) + 1);
			}
			if (!hasFound.containsKey(word)) {
				hasFound.put(word, 0);
			}
		}

		int left = 0, right = 0;
		while (right <= S.length() - wordLen) {
			String word = S.substring(right, right + wordLen);
			if (needToFind.containsKey(word)
					&& hasFound.get(word) < needToFind.get(word)) {
				right += wordLen;
				counter++;
				hasFound.put(word, hasFound.get(word) + 1);
			} else if (needToFind.containsKey(word)
					&& hasFound.get(word) >= needToFind.get(word)) {
				String leftWord = S.substring(left, left + wordLen);
				while (left <= S.length() - wordLen
						&& needToFind.containsKey(leftWord)) {
					if (!word.equals(leftWord)) {
						hasFound.put(leftWord, hasFound.get(leftWord) - 1);
						left = left + wordLen;
						counter--;
						leftWord = S.substring(left, left + wordLen);
					} else {
						break;
					}
				}
				right = right + wordLen;
				left = left + wordLen;
			} else {
				right++;
				left = right;
				counter = 0;
				for (String key : hasFound.keySet()) {
					hasFound.put(key, 0);
				}
				continue;
			}

			if (counter == L.length) {
				while (left <= S.length() - wordLen
						&& !needToFind.containsKey(S.substring(left, left
								+ wordLen))) {
					left++;
				}
				if (right - left == L.length * wordLen) {
					results.add(left);
				}
			}
		}

		return results;
	}
	/**
	 * 
	 */
	public SubstringWithConcatenationOfAllWords() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String S = "lingmindraboofooowingdingbarrwingmonkeypoundcake";
		String[] L = { "fooo", "barr", "wing", "ding", "wing" };
		PrintUtils.printList(findSubstring(S, L));

	}

}
